[Coding012] LeetCode 19

Remove Nth Node From End of List

More coding records

Get the knowledge flowing and circulating! :)

目录

题目：19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

xxxxxxxxxx
2
1
Input: head = [1,2,3,4,5], n = 2
2
Output: [1,2,3,5]

Example 2:

xxxxxxxxxx
2
1
Input: head = [1], n = 1
2
Output: []

Example 3:

xxxxxxxxxx
2
1
Input: head = [1,2], n = 1
2
Output: [1]

Constraints:

• The number of nodes in the list is sz.

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

Follow up: Could you do this in one pass?

代码1（配 · 手绘过程图）

xxxxxxxxxx
42
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode removeNthFromEnd(ListNode head, int n) {
13
        ListNode p = head;
14
        int len = 0;
15

16
        while (p != null)
17
        {
18
            len++;
19
            p = p.next;
20
        }
21

22
        // 特判： [1], n = 1; || [1], n = 2;
23
        if (len == 1 && len <= n) return null;  
24

25
        int x = len - n - 1;  // -1是因为，要锁定待删除结点的前一个结点
26

27
        // 特判：[1, 2], n = 2;
28
        if (x < 0) return head.next;  
29

30
        // 找到待删除结点的前一个结点，然后越过它
31
        ListNode q = head;
32
        while (x > 0)
33
        {            
34
            q = q.next;
35
            x--;
36
        }
37
        q.next = q.next.next;  // 越过待删除的结点；
38

39
        return head;
40
        
41
    }
42
}

代码解读：two pass解法

• 先遍历一遍链表，获取结点的总数；

• 然后通过数值计算，看看待删除结点从头开始数的话，处于第几个；

• 获取待删除结点的前一个结点，即可解答；

注意特判情况。

特殊测试样例：

xxxxxxxxxx
2
1
head = [1], n = 1
2
head = [1,2], n = 2

复杂度分析

$O(n)$$O(n)$, 但是最坏情况下，需要遍历2遍。

• 第一遍，确定整个链表的长度；

• 第二遍，找到待删除结点的前一个结点。

代码2（配 · 手绘过程图）

xxxxxxxxxx
40
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode removeNthFromEnd(ListNode head, int n) {
13

14
        // 感悟plus: 一定要加dummy结点！！！
15
        ListNode dummy = new ListNode(0);
16
        dummy.next = head;
17

18
        ListNode p = dummy;
19
        ListNode q = dummy;
20

21
        while (n > 0)  // 先走n步
22
        {
23
            n--;
24
            p = p.next;
25
        }
26

27
        while (p.next != null)  // 共同走剩下的步
28
        {
29
            p = p.next;
30
            q = q.next;
31
        }
32

33
        if (p.next == null)
34
        {
35
            q.next = q.next.next;
36
        }
37

38
        return dummy.next;        
39
    }
40
}

代码解读：one pass解法

• 双指针，首先让一个指针先跑x步（此时，剩下n-x步）；

• 然后让第二个指针开始加入奔跑行列，两个指针一起跑（跑完剩下的n-x步）；

  • 此时，第2个指针应该还剩x步没跑。即，当第一个指针跑到底的时候，第二个指针就指向待删除结点的前一个结点了！

搞定！

一定要加dummy结点，这样操作起来非常的舒服、丝滑！！！很重要！！！

复杂度分析

$O(n)$$O(n)$

一遍过！

★ 知识点积累 (Java)

1. 双指针的妙用

   • 一个先走，另一个后走；互补可以走完整个数组。

   • 一个从左向右 → ，一个从右向左 ←；（具体案例在后面再说）